在學習完陣列和鏈結串列之後呢，我們來把它們做統整比較吧!不過首先要先介紹一個網站，裡面整理了各式資料結構的時間複雜度並整理成表格。網站連結如下:

https://www.bigocheatsheet.com/

此圖片是網站的畫面截圖:

接著我們就要去分析陣列和鏈結串列的時間複雜度，做優缺點的分析:

Array

優點:

1. 隨機存取或已知查找目標索引時，只需要 O(1) 時間對 Array 的資料做存取。
2. 比 Linked list 為節省記憶體空間，因為 linked list 需要多一個指標 pointer 來記錄下一個節點的記憶體位置。

缺點:

1. 新增/刪除資料比較麻煩，若要在第一個位置新增資料，就需要把矩陣中所有元素往後移動，並且是O(N)的時間複雜度。同理，若要刪除第一個位置的資料，也需要 O(N) 的時間複雜度把矩陣中剩餘的元素往前移動。
2. 若時常在新增資料，要時常調整陣列的大小，會花費 O(N) 的時間在搬動資料(把資料從舊的陣列移動到新的陣列)。(ex: unshift() 函式，從前面加入陣列元素會把原本元素都往後推，O(n))

適用時機：

1. 隨機快速存取資料時
2. 已知資料的數量，如此便不用經常改變陣列大小
3. 要求記憶體空間的使用越少越好。

Linked list

優點：

1. 新增/刪除資料比 Array 簡單，只要對要新增刪除的相關節點們調整指標即可，不需要像 Array 搬動其餘元素。
2. linked list 的資料數量能動態的向記憶體要空間或釋放空間，不像 Array 會有 "重新定義陣列大小" 的問題。

缺點:

1. 因為 linked list 不能直接透過索引值找到某節點(ex: 像陣列可以透過 array[index] 找到要的元素)，若要找到特定節點，需要從頭開始找起，搜尋的時間複雜度為 O(N)。
2. 需要額外的記憶體空間來儲存指標。

Linked List 時間複雜度整理

• 插入節點: 開頭節點插入 O(1) or 其他位置 O(n)
• 刪除: 開頭節點刪除 O(1) or 其他位置 O(n)
• 搜尋: O(n)
• 取得: O(n)

適用時機：

1. 無法預期資料數量或頻繁變動資料數量時。
2. 需要頻繁地新增/刪除資料時。
3. 不需要快速查詢資料。

以上內容就是陣列和鏈結串列的比較，明天我們將來學習堆疊!